W9. Машины Тьюринга, теория автоматов, Алан Тьюринг и исторические предпосылки вычислений

1. Краткое содержание

1.1 Введение в теорию автоматов

1.1.1 Слово «автомат»

Слово automaton (мн. ч. automata) происходит от греч. αὐτόματον — «самодвижущийся», то есть действующий сам по себе. Оно вошло в латынь, а затем в современные европейские языки через латинизацию. Примечательно, что его впервые употребил Гомер (ок. 850 г. до н. э.), древнегреческий поэт, которому приписывают авторство «Илиады» и «Одиссеи» — древнейших известных литературных памятников Европы. В «Илиаде» Гомер описывает двери, открывающиеся сами собой, самоходные колёсные треноги и ожившие статуи. Идея машин, действующих без участия человека, столь же древна, как и само воображение человечества.

1.1.2 Что такое теория автоматов?

Теория автоматов — раздел теоретической информатики, в котором изучают:

• абстрактные математические машины (автоматы) и их возможности;
• вычислительные задачи, которые эти машины могут решать.

Автомат — это конечное описание формального языка, который сам может быть бесконечным. В этом главная мотивация: нужна компактная спецификация потенциально неограниченного объекта.

Есть две основные причины изучать теорию автоматов:

1. Теоретические модели вычислительных машин — автоматы дают аккуратные математические объекты, с помощью которых можно доказывать, что вычислимо, а что нет.
2. Практические приложения — на автоматах строятся компиляторы, верификация протоколов, проектирование систем и многое другое.

1.2 Модели вычислений

Модель вычислений — математическая схема, описывающая:

• как по входным данным получают выходы;
• как организованы единицы вычисления, память и обмен данными.

Модели вычислений изучают на трёх уровнях:

• Теория: теория автоматов, вычислимость, сложность вычислений.
• Практика: спецификация систем, построение компиляторов.

Существует много разных моделей. Основные семейства:

• Последовательные модели — выполняют по одному шагу:
  • конечные автоматы (FSA)
  • автоматы с магазином (PDA)
  • машины Тьюринга (TM)
• Функциональные модели — вычисление как вычисление математической функции:
  • λ-исчисление (Алонзо Чёрч, 1936)
• Параллельные / конкурентные модели — одновременная работа нескольких процессов:
  • сети Петри

Этот список не исчерпывающий; существуют сотни других моделей.

1.3 Иерархия Хомского: карта языков

Разные модели вычислений распознают разные классы языков. Иерархия Хомского упорядочивает эти классы от наиболее слабых (ограниченных) к наиболее мощным:

Иерархия Хомского: вложенные классы формальных языков и соответствующие им модели машин

Смысл этой схемы:

• Регулярные языки — распознаются FSA. FSA могут «считать» только до фиксированного числа (конечное число состояний — никакого произвольного \(n\)). Они справляются с шаблонами вроде «все строки, содержащие ab», но не с \(a^n b^n\).
• Контекстно-свободные языки — распознаются PDA. PDA справляются с \(a^n b^n\) за счёт стека. Однако PDA в общем случае не замкнуты относительно пересечения: если стек «настроен» под один шаблон, одновременно проверить другой нельзя. Поэтому \(a^n b^n c^n\) выходит за пределы PDA — память стека разрушительная (снятый символ теряется).
• Рекурсивно перечислимые языки — распознаются машинами Тьюринга. TM справляются с \(a^n b^n c^n\), потому что память на ленте неразрушительная: записанные символы остаются и могут многократно перечитываться.

1.4 Конечные автоматы (FSA): напоминание

Конечный автомат (FSA) — простейшая последовательная модель. Формально полный (детерминированный) FSA — это 5‑кортеж:

\[\langle Q, \Sigma, \delta, q_0, F \rangle\]

где:

• \(Q\) — конечное множество состояний;
• \(\Sigma\) — конечный входной алфавит;
• \(\delta : Q \times \Sigma \rightarrow Q\) — (полная) функция переходов;
• \(q_0 \in Q\) — начальное состояние;
• \(F \subseteq Q\) — множество принимающих состояний.

Главное ограничение: у FSA только фиксированная конечная память — текущее состояние. Нельзя сосчитать до произвольного \(n\), поэтому языки вроде \(a^n b^n\) недостижимы.

Применения FSA:

• Лексический анализ в компиляторах — сканирование исходного кода на лексемы (ключевые слова, идентификаторы, числа). Это первая фаза компиляции.
• Машины Мура/Мили — моделирование схем и электронных устройств. Машины Мили — это конечные преобразователи состояний с входной и выходной лентой.
• Проектирование и верификация систем — в UML state machines используется та же нотация для реактивных систем (например, контроллер температуры с состояниями Idle, Heating, Cooling, Error).
• Model checking ПО — автоматическая верификация реальных программ через построение конечных моделей. За эту технику была присуждена премия Тьюринга.

Пример — турникет с оплатой монетой: у турникета два состояния: Locked (заперт) и Unlocked (открыт). Вставка монеты ведёт из Locked в Unlocked; нажатие (толчок) — из Unlocked обратно в Locked. Любое другое действие (толчок в запертом состоянии, монета при уже открытом) даёт петлю на месте.

FSA турникета с оплатой монетой

FSA и верификация программ: задача верификации программ — даны программа \(P\) и спецификация \(S\); выполняет ли \(P\) условие \(S\)? — в общем случае неразрешима (следствие теоремы Райса, её разберём позже). Если же сузить модель вычислений с полной машины Тьюринга до FSA, задача верификации становится разрешимой. В этом идея model checking: обменивать выразительность на разрешимость.

1.5 Автоматы с магазином (PDA): напоминание

Автомат с магазином (PDA) расширяет FSA стеком. Формально детерминированный PDA — это 7‑кортеж:

\[\langle Q, I, \Gamma, \delta, q_0, Z_0, F \rangle\]

где:

• \(Q\) — конечное множество состояний;
• \(I\) — конечный входной алфавит;
• \(\Gamma\) — конечный алфавит магазина;
• \(\delta : Q \times (I \cup \{\varepsilon\}) \times \Gamma \rightarrow Q \times \Gamma^*\) — (частичная) функция переходов;
• \(q_0 \in Q\) — начальное состояние;
• \(Z_0 \in \Gamma\) — начальный символ магазина (маркер дна стека);
• \(F \subseteq Q\) — множество принимающих состояний.

PDA распознают контекстно-свободные языки; на этой модели строится синтаксический анализ в компиляторах — вторая фаза, которая проверяет, образуют ли лексемы корректную программу по грамматике.

Главное ограничение PDA: стек — разрушительная память. После снятия символа он исчезает. Поэтому PDA не может одновременно проверить два независимых счётных ограничения — для \(a^n b^n c^n\) уже нужна машина Тьюринга.

1.6 Машина Тьюринга: формальное определение

1.6.1 Мотивация

Машина Тьюринга (TM) — наиболее мощная последовательная модель вычислений. Она расширяет PDA, заменяя разрушительный стек лентой чтения/записи — потенциально бесконечной последовательностью ячеек с символами, над которыми головка может сдвигаться влево, вправо или оставаться на месте и перезаписывать любую ячейку. В отличие от стека (доступ только к вершине), лента позволяет многократно перечитывать ранее записанное.

TM была предложена Аланом Тьюрингом в 1936 году, чтобы дать точное математическое определение «что можно вычислить». Она намеренно проста — достаточно проста для теоретических рассуждений — и при этом достаточно мощна, чтобы симулировать любой современный язык программирования.

1.6.2 Формальное определение

(Детерминированная) машина Тьюринга с \(k\) лентами памяти — это 7‑кортеж:

\[T = \langle Q, I, \Gamma, \delta, q_0, Z_0, F \rangle\]

where:

• \(Q\) — конечное множество состояний;
• \(I\) — входной алфавит — символы, которые могут появляться на входной ленте;
• \(\Gamma\) — алфавит памяти — символы, которые можно записывать на ленты памяти (заметьте: \(\Gamma\) и \(I\) могут различаться);
• \(\delta\) — функция переходов (см. ниже);
• \(q_0 \in Q\) — начальное состояние;
• \(Z_0 \in \Gamma\) — начальный символ памяти — символ, изначально записанный на каждой ленте памяти (по аналогии с PDA его называют символом дна стека);
• \(F \subseteq Q\) — множество финальных (принимающих) состояний.

Сравнение определений FSA, PDA и TM:

Компонент	FSA	PDA	TM
Состояния \(Q\)	✓	✓	✓
Входной алфавит	\(\Sigma\)	\(I\)	\(I\)
Доп. алфавит памяти	—	\(\Gamma\) (стек)	\(\Gamma\) (лента)
Начальный символ памяти	—	\(Z_0\)	\(Z_0\)
Функция переходов	полная	частичная	частичная
Принимающие состояния \(F\)	✓	✓	✓

1.6.3 Функция переходов

Для TM с \(k\) лентами памяти функция переходов имеет вид:

\[\delta : (Q - F) \times (I \cup \{\_\}) \times (\Gamma \cup \{\_\})^k \rightarrow Q \times (\Gamma \cup \{\_\})^k \times \{R, L, S\}^{k+1}\]

Разбор по частям:

• Область определения: машина в состоянии \(q \notin F\) (ещё не в финальном), прочитала по одному символу с входной ленты и с каждой из \(k\) лент памяти.
• Область значений: машина переходит в новое состояние, записывает новые символы на каждую из \(k\) лент памяти и сдвигает каждую из \(k+1\) головок (входная + \(k\) памяти) в заданном направлении.

Три направления движения головки:

• \(R\) — на право на одну позицию;
• \(L\) — на лево на одну позицию;
• \(S\) — стоять (не двигаться).

Важные замечания:

• Функция переходов частичная: для некоторых комбинаций «состояние–вход» переход не задан. Если машина попадает в конфигурацию без применимого перехода, будучи не в финальном состоянии, она отвергает вход.
• Из финальных состояний нет исходящих переходов: достигнув финального состояния, машина останавливается.
• Символ \(\_ \notin \Gamma \cup I\) — специальный пустой символ (blank), обозначающий пустые ячейки. Ленты мыслятся бесконечными и заполненными пустыми символами за пределами записанного содержимого.

Для одноленточной TM (\(k = 1\)) функция переходов упрощается до:

\[\delta : (Q - F) \times (I \cup \{\_\}) \times (\Gamma \cup \{\_\}) \rightarrow Q \times (\Gamma \cup \{\_\}) \times \{R, L, S\}^2\]

1.6.4 Переходы на рисунке

Переход из состояния \(q\) в состояние \(q'\) изображают помеченной стрелкой:

\[q \xrightarrow{i,\; \langle A_1, \ldots, A_k \rangle \;/\; \langle A'_1, \ldots, A'_k \rangle,\; \langle M_0, M_1, \ldots, M_k \rangle} q'\]

где:

• \(q \in Q - F\) и \(q' \in Q\);
• \(i\) — входной символ, прочитанный с входной ленты;
• \(A_j\) — символ, прочитанный с \(j\)-й ленты памяти;
• \(A'_j\) — символ, записанный на \(j\)-ю ленту памяти (вместо \(A_j\));
• \(M_0\) — направление движения головки входной ленты;
• \(M_j\) — направление движения головки \(j\)-й ленты памяти;

при \(1 \leq j \leq k\).

Графическое изображение перехода TM: чтение входа i, символов лент A₁…Aₖ, запись A’₁…A’ₖ, движение головок M₀…Mₖ

1.6.5 Конфигурации

Конфигурация (снимок) TM в данный момент фиксирует всё, что нужно, чтобы продолжить вычисление: текущее состояние, содержимое всех лент и положение каждой головки.

Для TM с \(k\) лентами памяти конфигурация \(c\) — это \((k+2)\)‑кортеж:

\[c = \langle q,\; x \uparrow y,\; \alpha_1 \uparrow \beta_1,\; \ldots,\; \alpha_k \uparrow \beta_k \rangle\]

где:

• \(q \in Q\) — текущее состояние;
• \(x \uparrow y\) задаёт входную ленту: \(x\) — содержимое слева от головки, \(y = y' \cdot \_\) при \(y' \in I^*\) — содержимое справа (и под головкой). Символ \(\uparrow\) отмечает положение головки;
• \(\alpha_r \uparrow \beta_r\) аналогично задаёт \(r\)-ю ленту памяти;
• \(\uparrow \notin I \cup \Gamma\) — специальный маркер, используемый только в записи конфигураций (это не символ ленты).

Зачем нужны конфигурации: записав последовательность \(c_0 \vdash c_1 \vdash c_2 \vdash \ldots\), можно проследить вычисление TM по шагам. Так обычно объясняют и проверяют поведение TM.

1.6.6 Условие принятия

Пусть даны TM \(T = \langle Q, I, \Gamma, \delta, q_0, Z_0, F \rangle\) и входная строка \(s \in I^*\). Говорим, что \(s\) принимается машиной \(T\), если:

\[c_0 \vdash^* c_F\]

то есть из начальной конфигурации \(c_0\) за конечное число шагов можно попасть в финальную конфигурацию \(c_F\).

Начальная конфигурация \(c_0\):

\[c_0 = \langle q_0,\; \uparrow s,\; \uparrow Z_0,\; \ldots,\; \uparrow Z_0 \rangle\]

Головка входной ленты в начале строки \(s\); на каждой ленте памяти в начале символ \(Z_0\).

Финальная конфигурация \(c_F\):

\[c_F = \langle q,\; x \uparrow y,\; \alpha_1 \uparrow \beta_1,\; \ldots,\; \alpha_k \uparrow \beta_k \rangle \quad \text{where } q \in F\]

Конфигурация финальна тогда и только тогда, когда текущее состояние лежит в \(F\).

Язык, принимаемый машиной \(T\):

\[L(T) = \{s \in I^* \mid s \text{ is accepted by } T\}\]

1.7 Примеры машин Тьюринга

1.7.1 Пример: распознавание \(A^nB^n = \{a^n b^n \mid n > 0\}\)

Это одноленточная TM (\(k = 1\)). Стратегия:

1. Использовать ленту памяти как счётчик: за каждый a на входе записывать маркер M на ленту памяти.
2. Когда на входе начинаются b, двигать головку памяти назад и снимать по одному M на каждый b.
3. Принять вход, если он заканчивается ровно в момент, когда головка памяти вернулась к \(Z_0\).

Диаграмма состояний:

TM для языка aⁿbⁿ (n > 0): состояния q₀, q₁, q₂ и финальное qF

Трассировка для входа aabb:

\[\langle q_0, \uparrow aabb, \uparrow Z_0 \rangle \vdash\] \[\langle q_1, \uparrow aabb, Z_0 \uparrow \rangle \vdash\] \[\langle q_1, a \uparrow abb, Z_0 M \uparrow \rangle \vdash\] \[\langle q_1, aa \uparrow bb, Z_0 MM \uparrow \rangle \vdash\] \[\langle q_2, aa \uparrow bb, Z_0 M \uparrow M \rangle \vdash\] \[\langle q_2, aab \uparrow b, Z_0 \uparrow MM \rangle \vdash\] \[\langle q_2, aabb \uparrow, \uparrow Z_0 MM \rangle \vdash\] \[\langle q_F, aabb \uparrow, \uparrow Z_0 MM \rangle\]

Имеем \(c_0 \vdash^* c_F\), значит aabb принимается.

Как читать трассу: в каждой конфигурации символ сразу после \(\uparrow\) на входной ленте — тот, что сейчас под головкой входа. На ленте памяти символ сразу после \(\uparrow\) — под головкой памяти. Когда головка памяти доходит до \(Z_0\) после снятия всех маркеров M, машина переходит в \(q_F\).

1.7.2 Пример: распознавание \(A^nB^nC^n = \{a^n b^n c^n \mid n > 0\}\)

Этот язык нельзя распознать PDA (классический контекстно-зависимый пример), зато с ним справляется TM. Стратегия обобщает предыдущую: на ленте памяти считаем a, затем проверяем столько же b (снимая маркеры), затем столько же c (перечитывая и снимая оставшиеся маркеры).

Диаграмма состояний:

TM для языка aⁿbⁿcⁿ (n > 0): состояния от q₀ до q₃ и финальное qF

Частичная трассировка для входа aabbcc (начиная после фазы чтения b):

\[\langle q_2, aa \uparrow bbcc, Z_0 M \uparrow M \rangle \vdash\] \[\langle q_2, aab \uparrow bcc, Z_0 \uparrow MM \rangle \vdash\] \[\langle q_2, aabb \uparrow cc, \uparrow Z_0 MM \rangle \vdash\] \[\langle q_3, aabb \uparrow cc, Z_0 \uparrow MM \rangle \vdash\] \[\langle q_3, aabbc \uparrow c, Z_0 M \uparrow M \rangle \vdash\] \[\langle q_3, aabbcc \uparrow, Z_0 MM \uparrow \rangle \vdash\] \[\langle q_F, aabbcc \uparrow, Z_0 MM \uparrow \rangle\]

Вход aabbcc принимается.

Почему в \(q_3\) головка памяти движется вправо (а не влево): на фазе чтения a (\(q_1\)) головка памяти идёт вправо, записывая по одному M на каждый a. На фазе чтения b (\(q_2\)) головка идёт влево, снимая по одному M на каждый b. Войдя в \(q_3\) (при первом c), головка снова у \(Z_0\). Дальше снова движение вправо, снимая по одному оставшемуся M на каждый c. Такое повторное использование ленты и делает TM мощнее PDA.

1.8 Тезис Чёрча — Тьюринга

Тезис Чёрча — Тьюринга (его также называют тезисом Тьюринга) утверждает:

Функция на натуральных числах может быть вычислена эффективным методом тогда и только тогда, когда она вычислима на машине Тьюринга.

«Эффективный метод» означает алгоритм: конечную, детерминированную, пошаговую процедуру, которая всегда завершается с правильным ответом. Этот тезис не теорема — его нельзя формально доказать, потому что «эффективный метод» — неформальное понятие. Но более 80 лет он выдерживает проверку: любая предложенная модель вычислений (λ-исчисление, рекурсивные функции, современные CPU, Python, Haskell, …) оказывается по выразительной силе эквивалентна машинам Тьюринга.

Следствие для программирования: любую функцию, вычислимую на современном языке программирования, можно вычислить на TM, и наоборот. У TM и языков высокого уровня одинаковая выразительная сила. TM не предназначены для практического программирования — они нужны для доказательств: с ними проще рассуждать из-за простоты.

1.9 Алан Тьюринг: жизнь и наследие

Алан Тьюринг (23 июня 1912 — 7 июня 1954) — британский математик, логик и учёный в области вычислений. Он внёс фундаментальный вклад в четыре разные области:

• Вычислимость — машина Тьюринга и ответ на Entscheidungsproblem.
• Криптография — взлом немецкой шифровальной машины Enigma во Второй мировой войне.
• Искусственный интеллект — тест Тьюринга.
• Биоинформатика — математическое моделирование формирования биологических узоров.

Тьюринг жил и умер в Уилмслоу, недалеко от Манчестера (Великобритания); там синяя мемориальная доска гласит: «Основатель информатики и криптограф, чья работа была ключом к взлому военных шифров Enigma».

1.9.1 Вычислимость и машина Тьюринга

В 1936 году Тьюринг опубликовал работу «On Computable Numbers, with an Application to the Entscheidungsproblem» — одну из важнейших статей в истории математики. В ней он ввёл машину Тьюринга как математическую модель вычислений и показал, что у задачи разрешимости Гильберта нет общего алгоритмического решения (см. раздел 1.12).

1.9.2 Криптография: взлом Enigma

Во Вторую мировую войну Тьюринг работал в Government Code and Cypher School (GC&CS) в Блетчли-парке — центре британской криптоаналитики. Он возглавлял Hut 8, отдел, отвечавший за взлом немецких морских шифров.

Ключевые моменты этой истории:

• Enigma — немецкая электромеханическая шифровальная машина. Каждое сообщение шифровалось с ежедневно меняющимся ключом, давая на вид случайные символы.
• Польские математики уже выяснили основные принципы чтения сообщений Enigma и передали сведения британцам до войны.
• С началом войны Германия ежедневно меняла шифросистему, и старые методы перестали работать.
• Алан Тьюринг и Гордон Уэлчман спроектировали Bombe — электромеханическую машину, автоматически перебиравшую возможные настройки Enigma. К середине 1940 года сигналы люфтваффе регулярно читались.

Важный урок: за любым крупным достижением всегда стоит коллектив. Как документирует племянник Алана Дермот Тьюринг в книге «X, Y and Z: The Real Story of How Enigma Was Broken», заслуга принадлежит широкому сообществу — включая польских математиков, — а не одному гению в одиночку.

1.9.3 Искусственный интеллект: тест Тьюринга

В 1950 году Тьюринг опубликовал статью «Computing Machinery and Intelligence» в журнале Mind. Она начинается вопросом:

«Я предлагаю рассмотреть вопрос: могут ли машины мыслить?»

Поскольку «мышление» — слишком размытое понятие для прямой проверки, Тьюринг предложил игру в имитацию (сейчас её называют тестом Тьюринга):

• Человек-следователь (C) текстом общается с двумя скрытыми участниками: компьютером (A) и человеком (B).
• Следователь задаёт вопросы и пытается понять, кто есть кто.
• Если компьютер стабильно вводит следователя в заблуждение, заставляя думать, что он человек, машину считают интеллектуальной.

Тест Тьюринга (игра в имитацию): следователь C пытается отличить компьютер A от человека B по тексту

Тьюринг также отвечал на возражение леди Лавлейс — идею, что «машина может делать только то, что мы ей приказываем». Он считал, что возражение заслуживает серьёзного рассмотрения, но не опровергает возможность машинного интеллекта.

1.9.4 Биология и математический морфогенез

В 1952 году Тьюринг опубликовал «The Chemical Basis of Morphogenesis» — теперь это считают одной из основополагающих работ математической биологии. Он предположил, что сложные узоры у живых организмов — полосы зебры, пятна леопарда, расположение лепестков — могут возникать из простого математического механизма: систем реакции–диффузии.

Два химических вещества (он назвал их морфогены) диффундируют в ткани и реагируют друг с другом. При определённых условиях малые случайные флуктуации самопроизвольно усиливаются до устойчивых периодических структур. Это было биоинформатикой до биоинформатики — задолго до того, как у области появилось имя.

1.10 Исторический контекст: от людей-вычислителей до машин с хранимой программой

1.10.1 Люди-компьютеры

До электронных компьютеров слово computer обозначало человека, выполнявшего расчёты. В XIX — начале XX века (примерно до 1946 года) крупные организации содержали целые комнаты людей-вычислителей:

• Научные бюро, артиллерийские управления и актуарные фирмы организовывали вычисления как индустриальный процесс — своего рода фабрики вычислений.
• Работников выстраивали иерархически: на нижних уровнях считали вручную, на верхних проверяли и систематизировали результаты.
• Информацию рассматривали как индустриальный материал: стандартизировали, обрабатывали и передавали по цепочке, как на конвейере.

Так выглядела «бумажно-карандашная» индустриализация математики. Труд был монотонным и подверженным ошибкам.

1.10.2 ENIAC и первые компьютеры

Перелом произошёл в 1945 году с ENIAC (Electronic Numerical Integrator and Computer) — первым программируемым электронным универсальным цифровым компьютером.

• Ввод в ENIAC шёл через перфокарты — физические карты с отверстиями, кодирующими данные.
• Ранние программы вводили вручную, соединяя кабели (как на телефонной коммутаторной доске).
• Операторами ENIAC была команда женщин, ранее работавших людьми-вычислителями; они стали первыми в мире программистами электронных компьютеров.

1.10.3 Компьютер с хранимой программой

Ключевой концептуальный шаг — компьютер с хранимой программой: машина, в которой и команды программы, и данные лежат в одной памяти, а программу можно менять, изменяя память, а не перекоммутируя оборудование. Контрастируйте с ткацким станком Northrop, который всегда выполняет одну и ту же «программу ткачества», зашитую в физическую конструкцию.

1.10.4 Архитектура фон Неймана

Архитектура фон Неймана (имени Джона фон Неймана) — доминирующая модель компьютеров с хранимой программой:

• Центральный процессор (CPU), включающий:
  • устройство управления — выборка и декодирование команд из памяти;
  • арифметико-логическое устройство (ALU) — арифметические и логические операции.
• Блок памяти — хранит и данные, и команды программы в едином адресном пространстве.
• Устройства ввода и вывода.

Архитектура фон Неймана: устройство управления и ALU разделяют общую память для программы и данных

1.10.5 Гарвардская архитектура

Гарвардская архитектура разделяет пути хранения и сигналов для команд и данных на физически разные памяти:

• Память команд — хранит код программы; CPU только читает отсюда.
• Память данных — хранит значения; CPU читает и пишет.
• ALU, устройство управления и ввод-вывод — отдельные блоки с выделенными шинами.

Гарвардская архитектура: физически раздельные памяти для команд и данных

Главное отличие от фон Неймана: в гарвардской схеме нет риска случайно перезаписать команды данными (и наоборот), и CPU может одновременно выбирать команду и читать данные по разным шинам. Современные микроконтроллеры и DSP часто используют эту архитектуру.

1.10.6 TM и машины фон Неймана

TM и машины фон Неймана (VNM) эквивалентны по выразительной силе — они вычисляют один и тот же класс функций. Разница в доступе к памяти:

• TM: последовательный доступ — головка движется по ленте шаг за шагом.
• VNM: прямой (произвольный) доступ — к любому адресу памяти за один шаг.

Это различие не меняет класс разрешимых задач. Оно может влиять на вычислительную сложность (число шагов), но не на саму вычислимость. TM может симулировать VNM и наоборот.

Зачем тогда изучать TM? Из-за простоты они удобны для доказательств. Проще рассуждать об одной ленте и таблице переходов, чем о современном CPU с кэшами, конвейерами и прерываниями.

1.11 Общая модель многоленточной TM

Наиболее общая форма TM имеет:

• одну входную ленту — только чтение, головка движется влево/вправо;
• одну выходную ленту — только запись, головка движется вправо;
• \(k\) лент памяти — чтение/запись, головки движутся влево/вправо/стоят.

Все \(k+2\) головки управляются одним конечным автоматом (функцией переходов \(\delta\)). Это стандартная теоретическая модель в теории сложности.

В нашем курсе в основном работаем с TM с одной лентой памяти, для которых функция переходов имеет вид:

\[\delta : (Q - F) \times (I \cup \{\_\}) \times (\Gamma \cup \{\_\}) \rightarrow Q \times (\Gamma \cup \{\_\}) \times \{R, L, S\}^2\]

1.12 Математическая логика и Entscheidungsproblem

1.12.1 Principia Mathematica и мечта о формализации

В начале XX века математики стремились поставить всю математику на прочный логический фундамент. Бертран Рассел и Альфред Норт Уайтхед опубликовали Principia Mathematica (1910–1913) — монументальный труд на ~2000 страниц, в котором предпринималась попытка:

• аксиоматизировать всю математику — вывести любую истину из небольшого набора логических аксиом;
• доказать, что система полна (всякая истинная формула выводима) и непротиворечива (ложные формулы недоказуемы).

Философию этого направления называют логицизмом: вера в то, что математика сводится к чистой логике. Доказательная система опиралась на строгие формальные правила вывода, главным из которых был modus ponens. Работа была настолько дотошной, что вывод \(1 + 1 = 2\) занял сотни страниц символических выкладок — авторы с характерной британской сдержанностью заметили, что «приведённое утверждение время от времени полезно».

1.12.2 Программа Гильберта и Entscheidungsproblem

Давид Гильберт (1862–1943) — один из самых влиятельных математиков своей эпохи. В 1900 году он опубликовал 23 нерешённые задачи — дорожную карту математики XX века. В 1928 году вместе с Вильгельмом Аккерманом он сформулировал Entscheidungsproblem («проблему разрешимости»):

Найти алгоритм, который по данным предпосылкам — формулам логики первого порядка — и данному заключению определяет, выводимо ли это заключение из предпосылок по правилам логики первого порядка.

Иными словами: является ли математика полной, непротиворечивой и разрешимой? Гильберт спрашивал, существует ли механическая процедура, которая по любому математическому утверждению за конечное время выясняет, истинно оно или ложно.

Entscheidungsproblem: существует ли универсальный алгоритм, разрешающий любую математическую истину?

1.12.3 Крах программы: Гёдель и Тьюринг

Мечта о полной, непротиворечивой и разрешимой математике рухнула под ударом двух последовательных результатов:

1. Курт Гёдель (1931) — теоремы о неполноте: любая логическая система достаточной выразительности (способная выразить элементарную арифметику) неполна: существуют истинные утверждения, которые нельзя доказать внутри системы. Полнота и непротиворечивость не могут выполняться одновременно. Математику нельзя полностью аксиоматизировать.

   Сам Тьюринг отмечал связь, писал в статье 1936 года: «выводы поверхностно сходны с выводами Гёделя».

2. Чёрч и Тьюринг (1936) — неразрешимость Entscheidungsproblem: независимо Алонзо Чёрч (через λ-исчисление) и Алан Тьюринг (через машины Тьюринга) доказали, что общего алгоритма для проблемы разрешимости не существует. Доказательство Тьюринга строит конкретную задачу — проблему остановки — и показывает, что её нельзя разрешить ни одной TM.

Связь с верификацией программ: это напрямую касается разработки ПО. Задача верификации программ — даны \(P\) и спецификация \(S\); удовлетворяет ли \(P\) условию \(S\)? — эквивалентна вопросу, принимает ли TM определённый язык. Теорема Райса (будет позже) формулирует это так: любое нетривиальное семантическое свойство программ неразрешимо.

Формально:

\[P \text{ (программа)} \;\Updownarrow\; \text{TM}(P) \qquad S \text{ (спецификация)} \;\Updownarrow\; F(S) \text{ (формула 1-го порядка)}\] \[\text{Выполняется ли } \text{TM}(P) \vDash F(S)\text{? } \Rightarrow \textbf{НЕРАЗРЕШИМО}\]

Однако при ограничении модели вычислений с полной TM до конечного автомата задача верификации становится разрешимой. В этом смысл model checking — техники, удостоенной премии Тьюринга.

1.12.4 Тьюринг, Гёдель и бесконечность

Идеи Тьюринга связаны с глубокими вопросами о природе математики и сознания. Вопрос о том, превосходит ли человеческий разум машину Тьюринга, остаётся открытым:

• «Если у нас есть хоть одно свойство — пусть даже тривиальное, — которого нет у машин Тьюринга, то мы не можем быть просто машинами Тьюринга».

Это соприкасается с теорией бесконечных множеств (числа \(\aleph\) Кантора) и философией сознания — вопросами, которые работа Тьюринга подняла, но не решила; они по-прежнему активно обсуждаются.

---

2. Определения

• Automaton (автомат): абстрактная математическая машина, обрабатывающая входные символы и переходящая между состояниями по правилам.
• Automata Theory (теория автоматов): раздел теоретической информатики об абстрактных машинах (автоматах) и вычислительных задачах, которые они решают.
• Turing Machine (TM, машина Тьюринга): математическая модель вычислений: конечное множество состояний, входная лента, одна или несколько лент памяти с чтением/записью и функция переходов. Сильнейшая последовательная модель; задаёт границу алгоритмической вычислимости.
• Finite State Automaton (FSA): 5‑кортеж \(\langle Q, \Sigma, \delta, q_0, F \rangle\), распознающий регулярные языки при фиксированной конечной памяти (текущее состояние). Не может сосчитать до произвольного \(n\).
• Pushdown Automaton (PDA): 7‑кортеж \(\langle Q, I, \Gamma, \delta, q_0, Z_0, F \rangle\), расширяющий FSA стеком LIFO; распознаёт контекстно-свободные языки.
• Input Alphabet (\(I\) или \(\Sigma\)): конечное множество символов входной ленты.
• Memory Alphabet (\(\Gamma\)): конечное множество символов, записываемых на лент(ы) памяти TM или PDA; отличается от входного алфавита.
• Blank Symbol (\(\_\)): специальный символ (\(\_ \notin \Gamma \cup I\)) для пустых ячеек; ленты бесконечны и заполнены пустыми ячейками за пределами записи.
• Initial Memory Symbol (\(Z_0\)): символ в начале каждой ленты памяти при старте TM; маркер дна ленты.
• Transition Function (\(\delta\)): частичная функция, задающая поведение TM: по текущему состоянию и символам под головками — следующее состояние, новые символы и движения головок.
• Configuration (Snapshot) (конфигурация): \((k+2)\)‑кортеж \(\langle q, x \uparrow y, \alpha_1 \uparrow \beta_1, \ldots, \alpha_k \uparrow \beta_k \rangle\) — полное состояние TM: состояние, ленты, положения головок.
• Initial Configuration (\(c_0\)) (начальная конфигурация): \(\langle q_0, \uparrow s, \uparrow Z_0, \ldots, \uparrow Z_0 \rangle\), где \(s\) — входная строка.
• Final Configuration (\(c_F\)) (финальная конфигурация): любая конфигурация с состоянием \(q \in F\).
• Acceptance (принятие): строка \(s\) принимается TM \(T\), если \(c_0 \vdash^* c_F\) — за конечное число шагов достижима финальная конфигурация.
• \(\vdash\) (отношение шага): один шаг вычисления TM (\(c \vdash c'\) — за один шаг из \(c\) в \(c'\)).
• \(\vdash^*\) (рефлексивно-транзитивное замыкание): ноль или более шагов.
• Chomsky Hierarchy (иерархия Хомского): классификация формальных языков по выразительной силе: регулярные (FSA) \(\subset\) КС (PDA) \(\subset\) рекурсивно перечислимые (TM).
• Church–Turing Thesis (тезис Чёрча — Тьюринга): неформальное утверждение, что всякая эффективно вычислимая функция вычислима на TM. Не теорема (формально не доказывается), но общепринято.
• Entscheidungsproblem: проблема разрешимости Гильберта (1928): существует ли алгоритм, который по любому математическому утверждению определяет, выводимо ли оно из аксиом? Ответ: нет (Чёрч, Тьюринг, 1936).
• Gödel’s Incompleteness Theorems (теоремы Гёделя о неполноте): два результата (1931): любая достаточно мощная формальная система либо неполна (есть недоказуемые истины), либо противоречива (доказуемы ложные утверждения).
• Turing Test (Imitation Game) (тест Тьюринга): критерий «интеллекта» машины (1950): если компьютер вводит человека-следователя в заблуждение, его считают интеллектуальным.
• Model Checking: автоматическая проверка, удовлетворяет ли конечная модель системы спецификации. Разрешимо (в отличие от общей верификации программ), так как модель ограничена уровнем FSA.
• Von Neumann Architecture: архитектура с единой памятью для команд и данных и CPU (устройство управления + ALU).
• Harvard Architecture: архитектура с физически раздельными путями и памятью для команд и данных; возможна одновременная выборка команды и доступ к данным.
• Stored-Program Computer: компьютер, в котором команды хранятся в памяти и могут изменяться (в отличие от жёстко «прошитых» программ).
• Reaction-Diffusion System (система реакции–диффузии): модель Тьюринга (1952) биологических узоров: два морфогена диффундируют и реагируют, порождая периодические пространственные структуры (полосы, пятна).

---

3. Формулы

• Определение TM (\(k\) лент): \(T = \langle Q, I, \Gamma, \delta, q_0, Z_0, F \rangle\)
• Функция переходов (\(k\) лент памяти): \(\delta : (Q - F) \times (I \cup \{\_\}) \times (\Gamma \cup \{\_\})^k \rightarrow Q \times (\Gamma \cup \{\_\})^k \times \{R, L, S\}^{k+1}\)
• Функция переходов (1 лента памяти): \(\delta : (Q - F) \times (I \cup \{\_\}) \times (\Gamma \cup \{\_\}) \rightarrow Q \times (\Gamma \cup \{\_\}) \times \{R, L, S\}^2\)
• Конфигурация (\(k\) лент памяти): \(c = \langle q, x \uparrow y, \alpha_1 \uparrow \beta_1, \ldots, \alpha_k \uparrow \beta_k \rangle\)
• Начальная конфигурация: \(c_0 = \langle q_0, \uparrow s, \uparrow Z_0, \ldots, \uparrow Z_0 \rangle\)
• Условие принятия: \(s \in L(T) \iff c_0 \vdash^* c_F\), где \(c_F = \langle q, \ldots \rangle\) при \(q \in F\)
• Язык TM: \(L(T) = \{s \in I^* \mid s \text{ is accepted by } T\}\)
• Определение FSA: \(\langle Q, \Sigma, \delta, q_0, F \rangle\) с \(\delta : Q \times \Sigma \rightarrow Q\)
• Определение PDA: \(\langle Q, I, \Gamma, \delta, q_0, Z_0, F \rangle\) с \(\delta : Q \times (I \cup \{\varepsilon\}) \times \Gamma \rightarrow Q \times \Gamma^*\)

---

4. Примеры

4.1. Спроектировать TM для \(L_1 = \{wcw \mid w \in \{a,b\}^+\}\) (Лаба 8, Задание 1)

Спроектируйте машину Тьюринга, распознающую \(L_1 = \{wcw \mid w \in \{a, b\}^+\}\). Язык состоит из строк, где непустое слово \(w\) над \(\{a, b\}\) повторяется дважды, разделённые символом c. Примеры: aca (\(w = a\)), abcab (\(w = ab\)), bcb (\(w = b\)). Опишите стратегию и ключевые переходы.

Показать решение

Идея: чтобы проверить \(wcw\), копируем первую половину в память, затем посимвольно сравниваем вторую половину с памятью.

Стратегия TM для wcw: копирование левого блока, затем сравнение с правым

Стратегия (1 лента памяти):

1. Фаза копирования (\(q_0\)): читать символы до c с входа, записывая каждый на ленту памяти. Обе головки движутся вправо.
2. Фаза перемотки (\(q_1\)): при встрече c вернуть головку памяти к \(Z_0\) (перемотка).
3. Фаза сравнения (\(q_2\)): синхронно двигать вход и память вправо, сравнивая символы.
4. Принятие (\(q_F\)): если одновременно на входе и в памяти достигнут пустые ячейки.

Ключевые переходы:

• \((q_0, a, \_) \rightarrow (q_0, a, \langle R, R \rangle)\) — копировать a в память.
• \((q_0, b, \_) \rightarrow (q_0, b, \langle R, R \rangle)\) — копировать b в память.
• \((q_0, c, \_) \rightarrow (q_1, \_, \langle R, L \rangle)\) — разделитель; начать перемотку памяти.
• \((q_1, i, X) \rightarrow (q_1, X, \langle S, L \rangle)\) при \(X \neq Z_0\) — перемотка памяти.
• \((q_1, i, Z_0) \rightarrow (q_2, Z_0, \langle S, R \rangle)\) — память в начале; начать сравнение.
• \((q_2, a, a) \rightarrow (q_2, a, \langle R, R \rangle)\) — совпадение a.
• \((q_2, b, b) \rightarrow (q_2, b, \langle R, R \rangle)\) — совпадение b.
• \((q_2, \_, \_) \rightarrow (q_F, \_, \langle S, S \rangle)\) — обе ленты исчерпаны: принять.
• Любое несовпадение: перехода нет; отвергнуть.

Ответ: TM записывает первую половину в память, перематывает, затем посимвольно сравнивает. Принимает тогда и только тогда, когда строка имеет вид \(wcw\) с одинаковыми половинами.

4.2. Спроектировать TM для \(L_5 = \{(ab)^n \mid n \geq 0\}\) (Лаба 8, Домашнее задание 1)

Спроектируйте TM, распознающую \(L_5 = \{(ab)^n \mid n \geq 0\}\) — строки из нуля и более повторений ab: \(\varepsilon\), ab, abab, ababab, …

Показать решение

Идея: \(L_5\) — на самом деле регулярный язык; его распознаёт FSA с тремя состояниями. TM может использовать ту же логику конечного управления. Лента памяти не нужна.

Вид конечного управления TM для языка (ab)ⁿ

Наглядно как у FSA:

• Состояние \(q_0\) (старт, принимающее): ожидается a или конец строки.
• Состояние \(q_1\): только что прочитан a, ожидается b.
• Любой другой символ ведёт в мёртвое (отвергающее) состояние.

Переходы TM (лента памяти не нужна или игнорируется):

• \((q_0, \_, Z_0/Z_0, \langle S, S \rangle) \rightarrow q_F\) — пустой вход: принять (\(n = 0\)).
• \((q_0, a, Z_0/Z_0, \langle R, S \rangle) \rightarrow q_1\) — прочитан a, переход в \(q_1\).
• \((q_1, b, Z_0/Z_0, \langle R, S \rangle) \rightarrow q_0\) — после a прочитан b, возврат в \(q_0\).
• Все прочие переходы: не определены (отвергнуть).

Вернувшись в \(q_0\) после чтения b, если вход пуст: принять. Иначе продолжать.

Ответ: TM чередует ожидание a (состояние \(q_0\)) и b (\(q_1\)). Принимает тогда и только тогда, когда вход заканчивается в \(q_0\) (все пары завершены). Для этого регулярного языка лента памяти не нужна.

4.3. Спроектировать TM для \(L_2 = \{wcw^R \mid w \in \{a,b\}^+\}\) (Лаба 8, Задание 2)

Спроектируйте TM, распознающую \(L_2 = \{wcw^R \mid w \in \{a,b\}^+\}\), где \(w^R\) — обращение строки \(w\). Примеры: abcba (\(w = ab\)), bcb (\(w = b\)). Опишите стратегию и ключевые переходы.

Показать решение

Идея: \(wcw^R\) проверяют, копируя \(w\) в память (слева направо), затем читая вторую половину входа при движении по памяти справа налево — ведь \(w^R\), читаемое слева направо, согласуется с \(w\), читаемым справа налево.

Стратегия TM для wcwᴿ: сравнение второго блока с памятью в обратном направлении

Стратегия (1 лента памяти):

1. Фаза копирования (\(q_0\)): читать символы до c, писать в память (обе головки вправо).
2. На c: оставить головку памяти на месте (сразу после последнего символа \(w\)), сдвинуть вход. Переход к фазе сравнения.
3. Фаза сравнения (\(q_1\)): вход движется вправо (читается \(w^R\) слева направо), память — влево (читается \(w\) справа налево). На каждом шаге сравнение.
4. Принятие (\(q_F\)): на входе пусто, в памяти у \(Z_0\).

Ключевые переходы:

• \((q_0, a, \_) \rightarrow (q_0, a, \langle R, R \rangle)\) — копировать a.
• \((q_0, b, \_) \rightarrow (q_0, b, \langle R, R \rangle)\) — копировать b.
• \((q_0, c, \_) \rightarrow (q_1, \_, \langle R, L \rangle)\) — найден c; вход проходит c, память на шаг назад к последнему символу \(w\).
• \((q_1, a, a) \rightarrow (q_1, a, \langle R, L \rangle)\) — совпадение a: вход вправо, память влево.
• \((q_1, b, b) \rightarrow (q_1, b, \langle R, L \rangle)\) — совпадение b.
• \((q_1, \_, Z_0) \rightarrow (q_F, Z_0, \langle S, S \rangle)\) — достигнуты оба конца: принять.

Ответ: TM «укладывает» \(w\) на ленту памяти и сопоставляет обращённую половину с вершины к низу. Принимает тогда и только тогда, когда строка имеет вид \(wcw^R\).

4.4. Спроектировать TM для \(L_6 = \{a^n b^{2n} c^{3n} \mid n \geq 0\}\) (Лаба 8, Домашнее задание 2)

Спроектируйте TM, распознающую \(L_6 = \{a^n b^{2n} c^{3n} \mid n \geq 0\}\). Примеры: \(\varepsilon\) (\(n=0\)), abbccc (\(n=1\)), aabbbbcccccc (\(n=2\)). Подробно опишите стратегию.

Показать решение

Идея: обобщение схемы для \(a^n b^n c^n\) с соотношением \(1:2:3\). TM кодирует это соотношение прямо на ленте памяти, записывая разное число маркеров на каждый a.

Раскладка памяти TM для проверки языка aⁿb²ⁿc³ⁿ

Стратегия:

На каждый a на входе записываем на ленту памяти две маркеры B и три маркеры C. Далее:

• каждый b снимает одну маркер B;
• каждый c снимает одну маркер C;
• принимаем, когда одновременно исчерпаны вход и память.

Раскладка ленты памяти после чтения \(n\) символов a: \(Z_0 \underbrace{BB \cdots B}_{2n} \underbrace{CC \cdots C}_{3n}\)

Фазы:

1. Фаза a (\(q_0\)): на каждый a записать в память BB + CCC (5 шагов по памяти на символ входа). Сдвинуть вход.
2. Фаза b (\(q_1\)): на каждый b снять одну B с памяти (дойти вправо до следующей B, стереть).
3. Переход к фазе c: когда все B сняты (головка у первой C), перейти в \(q_2\).
4. Фаза c (\(q_2\)): на каждый c снять одну C.
5. Принятие (\(q_F\)): вход пуст и память пуста одновременно.

Ключевые переходы (схематично):

• \((q_0, a, \_) \rightarrow\) записать B, сдвинуть память, записать B, сдвинуть память, записать C, C, C; затем сдвинуть вход; вернуться в \(q_0\).
• \((q_0, b, B) \rightarrow (q_1, \_, \langle R, R \rangle)\) — первый b; начать снимать B.
• \((q_1, b, B) \rightarrow (q_1, \_, \langle R, R \rangle)\) — снять следующую B.
• \((q_1, c, C) \rightarrow (q_2, \_, \langle R, R \rangle)\) — все B сняты; начать снимать C.
• \((q_2, c, C) \rightarrow (q_2, \_, \langle R, R \rangle)\) — снять следующую C.
• \((q_2, \_, Z_0) \rightarrow (q_F, Z_0, \langle S, S \rangle)\) — принять.

Ответ: TM кодирует соотношение \(1:2:3\) прямо в раскладке памяти. Техника обобщается на любой язык с фиксированными пропорциями \(a^n b^{kn} c^{mn}\): на каждый a писать \(k\) маркеров B и \(m\) маркеров C.

4.5. Спроектировать TM для палиндромов (Лаба 8, Задание 3)

Спроектируйте TM, распознающую \(L_3 = \{w \mid w \in \{a,b\}^*,\; w \text{ — палиндром}\}\). Палиндром читается одинаково слева направо и справа налево. Примеры: \(\varepsilon\), a, b, aba, abba. Опишите стратегию.

Показать решение

Идея: для палиндрома \(w = w^R\). Проверку палиндрома можно свести к проверке вида \(wcw^R\), сохранив строку в памяти и сравнив её с обращением.

Стратегия TM для палиндрома: копия слова сравнивается с исходником при чтении входа назад

Стратегия (1 лента памяти):

1. Фаза копирования (\(q_0\)): скопировать весь вход на ленту памяти (обе головки вместе вправо).
2. Перемотка памяти (\(q_1\)): после полного чтения входа вернуть головку памяти к \(Z_0\).
3. Фаза сравнения (\(q_2\)): одновременно двигать головку памяти вперёд и головку входа назад, сравнивая символы.
4. Принятие (\(q_F\)): головки встречаются в середине (или одновременно достигают \(Z_0\) и пустого символа).

Замечание: у TM головка входа может двигаться влево, в отличие от обычного FSA или PDA. Такой двунаправленный доступ — часть большей мощности TM.

Альтернатива — двухпроходное сравнение:

1. Найти центр строки (чередуя движения вперёд и назад).
2. Сравнивать первый символ с последним, второй с предпоследним и т. д.

Смысл: проверка палиндрома для \(w\) эквивалентна проверке \(w = w^R\). Поскольку TM могут перечитывать ленты, это делается естественно: в памяти хранится \(w\); после перемотки память читается вперёд, а вход сравнивается в обратном порядке.

Ответ: TM принимает тогда и только тогда, когда вход — палиндром. Лента памяти хранит копию \(w\), читаемую вперёд при сравнении с входом, читаемым назад.

4.6. Спроектировать TM для \(L_4 = \{a^n b^n \mid n \geq 0\} \cup \{a^n b^{2n} \mid n \geq 0\}\) (Лаба 8, Задание 4)

Спроектируйте TM, распознающую \(L_4 = \{a^n b^n \mid n \geq 0\} \cup \{a^n b^{2n} \mid n \geq 0\}\). Объясните, почему здесь нужна TM (и почему одним детерминированным PDA это не обойти просто), и опишите стратегию TM.

Показать решение

Идея: для объединения \(\{a^n b^n\} \cup \{a^n b^{2n}\}\) нужно проверить два разных счётных условия. Детерминированный PDA не может сделать это за один проход: стек по-разному настраивается под каждую альтернативу. TM может перечитать ленту и по сути последовательно испробовать обе стратегии.

TM для {aⁿbⁿ} ∪ {aⁿb²ⁿ}: одна стратегия подсчёта, сброс, затем другая

Почему одному детерминированному PDA трудно: после чтения блока a и помещения \(n\) маркеров в стек PDA должен решить, ожидать \(n\) или \(2n\) символов b. В детерминированном случае решение нужно принять, ещё не видя b — это невозможно. Недетерминированный PDA мог бы «угадывать»; детерминированная TM может сначала проверить один вариант, затем другой.

Стратегия TM:

Фаза 1: проверка \(a^n b^n\)

1. На каждый a записать в память один M. Обе головки вправо.
2. На каждый b снять один M (память влево). Вход вправо.
3. Если вход кончился и память у \(Z_0\): принять (случай \(n = 0\): сразу пусто).
4. Если вход кончился, а в памяти ещё есть M: отвергнуть.
5. Если b кончились, а M ещё есть: перейти к фазе 2 (предварительно сброс).

Фаза 2: проверка \(a^n b^{2n}\)

1. Сброс: перемотать память к \(Z_0\); вернуть головку входа в начало.
2. На каждый a записать один M в память.
3. На каждую пару b снять один M.
4. Если вход кончился, память у \(Z_0\) и число прочитанных b чётно: принять.
5. Иначе: отвергнуть.

Ответ: возможность TM перечитывать и перематывать ленты позволяет проверять несколько гипотез подряд. Это сила неразрушительного двунаправленного доступа к ленте — недоступного PDA с разрушительным однонаправленным стеком.

4.7. Трассировка TM на \(a^n b^n\) (Лекция 8, Пример 1)

Рассмотрим TM \(T\), распознающую \(A^n B^n = \{a^n b^n \mid n > 0\}\), с переходами (1 лента памяти):

• \(q_0 \xrightarrow{a,\, Z_0/Z_0,\, \langle S,R \rangle} q_1\)
• \(q_1 \xrightarrow{a,\, \_/M,\, \langle R,R \rangle} q_1\) (петля)
• \(q_1 \xrightarrow{b,\, \_/\_,\, \langle S,L \rangle} q_2\)
• \(q_2 \xrightarrow{b,\, M/M,\, \langle R,L \rangle} q_2\) (петля)
• \(q_2 \xrightarrow{\_,\, Z_0/Z_0,\, \langle S,S \rangle} q_F\)

Выполните трассировку на входе \(s = aabb\). Выпишите все конфигурации \(c_0 \vdash c_1 \vdash \ldots \vdash c_F\).

Показать решение

Идея: на ленте памяти считаем a, записывая маркеры M. В каждой конфигурации символ \(\uparrow\) отмечает положение головки.

Фазы управления при трассировке TM для aⁿbⁿ

1. Начальная конфигурация: \[c_0 = \langle q_0,\; \uparrow aabb,\; \uparrow Z_0 \rangle\]
2. \(q_0\) читает a, память читает \(Z_0\): переход в \(q_1\), головка памяти вправо, головка входа на месте. \[c_1 = \langle q_1,\; \uparrow aabb,\; Z_0 \uparrow \rangle\]
3. \(q_1\) читает a, память читает _ (пусто): записать M, обе головки вправо. \[c_2 = \langle q_1,\; a \uparrow abb,\; Z_0 M \uparrow \rangle\]
4. \(q_1\) читает a, память читает _: записать M, обе головки вправо. \[c_3 = \langle q_1,\; aa \uparrow bb,\; Z_0 MM \uparrow \rangle\]
5. \(q_1\) читает b, память читает _: вход на месте, головка памяти влево. Переход в \(q_2\). \[c_4 = \langle q_2,\; aa \uparrow bb,\; Z_0 M \uparrow M \rangle\]
6. \(q_2\) читает b, память читает M: вход вправо, головка памяти влево. \[c_5 = \langle q_2,\; aab \uparrow b,\; Z_0 \uparrow MM \rangle\]
7. \(q_2\) читает b, память сдвигается влево мимо \(Z_0\). \[c_6 = \langle q_2,\; aabb \uparrow,\; \uparrow Z_0 MM \rangle\]
8. \(q_2\) читает _ (конец входа), память читает \(Z_0\): переход в \(q_F\). \[c_7 = \langle q_F,\; aabb \uparrow,\; \uparrow Z_0 MM \rangle\]

Имеем \(c_0 \vdash^* c_F\).

Ответ: строка aabb принимается. Машина записала 2 маркера M (по одному на каждый a), сняла их при чтении двух b и достигла \(q_F\), когда вход исчерпан, а головка памяти вернулась к \(Z_0\).

4.8. Трассировка TM на \(a^n b^n c^n\) (Лекция 8, Пример 2)

Рассмотрим TM \(T\), распознающую \(A^n B^n C^n = \{a^n b^n c^n \mid n > 0\}\), с переходами:

• \(q_0 \xrightarrow{a,\, Z_0/Z_0,\, \langle S,R \rangle} q_1\)
• \(q_1 \xrightarrow{a,\, \_/M,\, \langle R,R \rangle} q_1\)
• \(q_1 \xrightarrow{b,\, \_/\_,\, \langle S,L \rangle} q_2\)
• \(q_2 \xrightarrow{b,\, M/M,\, \langle R,L \rangle} q_2\)
• \(q_2 \xrightarrow{c,\, Z_0/Z_0,\, \langle S,R \rangle} q_3\)
• \(q_3 \xrightarrow{c,\, M/M,\, \langle R,R \rangle} q_3\)
• \(q_3 \xrightarrow{\_,\, \_/\_,\, \langle S,S \rangle} q_F\)

Дайте частичную трассировку на входе \(s = aabbcc\), начиная с конфигурации \(\langle q_2, aa \uparrow bbcc, Z_0 M \uparrow M \rangle\).

Показать решение

Идея: к машине для \(a^n b^n\) добавлена третья фаза. После чтения всех b и возврата головки памяти к \(Z_0\) машина входит в \(q_3\) и читает c, снова двигая головку памяти вправо — второй раз «съедая» маркеры M.

Трёхфазная TM для aⁿbⁿcⁿ

Начиная с \(\langle q_2, aa \uparrow bbcc, Z_0 M \uparrow M \rangle\):

1. \(q_2\) читает b, память читает M: вход вправо, память влево. \[\langle q_2,\; aab \uparrow bcc,\; Z_0 \uparrow MM \rangle\]
2. \(q_2\) читает b, память читает \(Z_0\)… головка памяти сдвинулась влево к \(Z_0\). \[\langle q_2,\; aabb \uparrow cc,\; \uparrow Z_0 MM \rangle\]
3. \(q_2\) читает c, память читает \(Z_0\): переход в \(q_3\), головки на месте. \[\langle q_3,\; aabb \uparrow cc,\; Z_0 \uparrow MM \rangle\]
4. \(q_3\) читает c, память читает M: вход вправо, память вправо. \[\langle q_3,\; aabbc \uparrow c,\; Z_0 M \uparrow M \rangle\]
5. \(q_3\) читает c, память читает M: вход вправо, память вправо. \[\langle q_3,\; aabbcc \uparrow,\; Z_0 MM \uparrow \rangle\]
6. \(q_3\) читает _, память читает _: переход в \(q_F\). \[\langle q_F,\; aabbcc \uparrow,\; Z_0 MM \uparrow \rangle\]

Ответ: строка aabbcc принимается. Лента памяти \(Z_0 MM\) кодирует \(n = 2\). Маркеры M проходятся один раз на фазе b (справа налево) и один раз на фазе c (слева направо). Вход и память исчерпываются одновременно.

4.9. Спроектировать TM для \(L = \{a^n b^n \mid n > 0\}\) (Туториал 8, Пример 1)

Спроектируйте детерминированную машину Тьюринга, распознающую язык \(L = \{a^n b^n \mid n > 0\}\).

Показать решение

Идея: классический нерегулярный контекстно-свободный язык. TM справляется, используя ленту как счётчик — помечая согласованные пары \(a\) и \(b\).

Цикл одноленточной TM для aⁿbⁿ

Идея: многократно сканировать ленту: пометить одну несопоставленную \(a\) (заменить на \(M\)), затем найти вправо и пометить одну несопоставленную \(b\) (заменить на \(M\)), вернуться влево. Принять, когда все символы помечены.

Состояния: \(q_0\) (искать \(a\)), \(q_1\) (искать \(b\) вправо), \(q_2\) (возврат влево), \(q_F\) (принять), \(q_{reject}\) (отвергнуть).

Функция переходов:

Состояние	Чтение	Запись	Движение	Далее
\(q_0\)	\(a\)	\(M\)	R	\(q_1\)
\(q_0\)	\(M\)	\(M\)	R	\(q_0\)
\(q_0\)	\(\sqcup\)	\(\sqcup\)	S	\(q_F\)
\(q_1\)	\(a\)	\(a\)	R	\(q_1\)
\(q_1\)	\(M\)	\(M\)	R	\(q_1\) (пропуск помеченных \(b\))
\(q_1\)	\(b\)	\(M\)	L	\(q_2\)
\(q_1\)	\(\sqcup\)	\(\sqcup\)	S	\(q_{reject}\)
\(q_2\)	\(a\)	\(a\)	L	\(q_2\)
\(q_2\)	\(M\)	\(M\)	L	\(q_2\)
\(q_2\)	\(\sqcup\)	\(\sqcup\)	R	\(q_0\)

Условие принятия: в \(q_0\), если остались только \(M\) (следующий непрочитанный — \(\sqcup\)), принять. Отвергнуть при несопоставленной \(b\) или лишней \(a\).

Трасса на \(aabb\):

\[\sqcup \underline{a}abb\sqcup \xrightarrow{q_0} \sqcup M\underline{a}bb\sqcup \xrightarrow{q_1} \sqcup Ma\underline{b}b\sqcup \xrightarrow{q_1,\text{метка}} \sqcup Ma\underline{M}b\sqcup \xrightarrow{q_2} \sqcup \underline{M}aMb\sqcup \xrightarrow{q_2,\text{возврат}} \sqcup \underline{M}aMb\]

Далее: пометить вторую \(a\) → найти вторую \(b\) → всё помечено → принять.

4.10. Спроектировать TM для \(L = \{a^n b^n c^n \mid n > 0\}\) (Туториал 8, Пример 2)

Спроектируйте TM, распознающую контекстно-зависимый язык \(L = \{a^n b^n c^n \mid n > 0\}\).

(Замечание: этот язык не распознаётся ни конечным автоматом, ни автоматом с магазином — только машина Тьюринга.)

Показать решение

Идея: расширить схему для \(a^n b^n\) третьей фазой: на каждом проходе помечаются по одной \(a\), одной \(b\) и одной \(c\).

Цикл одноленточной TM для aⁿbⁿcⁿ

Идея: на каждой итерации основного цикла: 1. Идти вправо, пометить крайнюю слева немаркированную \(a\) символом \(X\). 2. Далее вправо — крайнюю немаркированную \(b\) как \(Y\). 3. Далее вправо — крайнюю немаркированную \(c\) как \(Z\). 4. Просканировать всю ленту влево к началу. 5. Повторять. Принять, когда не осталось немаркированных \(a\) и все \(b\) и \(c\) тоже полностью помечены.

Состояния: \(q_0\) (искать \(a\)), \(q_1\) (искать \(b\)), \(q_2\) (искать \(c\)), \(q_3\) (возврат влево), \(q_4\) (проверка: только \(Y\) и \(Z\)), \(q_F\) (принять).

Функция переходов (высокий уровень):

Состояние	Чтение	Запись	Движение	Далее
\(q_0\)	\(a\)	\(X\)	R	\(q_1\)
\(q_0\)	\(X\)	\(X\)	R	\(q_0\) (пропуск помеченных \(a\))
\(q_0\)	\(Y\)	\(Y\)	R	\(q_4\) (больше нет \(a\) — проверить остальное)
\(q_1\)	\(a\)	\(a\)	R	\(q_1\)
\(q_1\)	\(Y\)	\(Y\)	R	\(q_1\) (пропуск помеченных \(b\))
\(q_1\)	\(b\)	\(Y\)	R	\(q_2\)
\(q_2\)	\(b\)	\(b\)	R	\(q_2\)
\(q_2\)	\(Z\)	\(Z\)	R	\(q_2\) (пропуск помеченных \(c\))
\(q_2\)	\(c\)	\(Z\)	L	\(q_3\)
\(q_3\)	любой	тот же	L	\(q_3\) (скан до левого края)
\(q_3\)	\(\sqcup\)	\(\sqcup\)	R	\(q_0\)
\(q_4\)	\(Y\)	\(Y\)	R	\(q_4\)
\(q_4\)	\(Z\)	\(Z\)	R	\(q_4\)
\(q_4\)	\(\sqcup\)	\(\sqcup\)	S	\(q_F\)

Отвергнуть, если в какой-то момент не найден ожидаемый символ (например, нет \(b\) или \(c\), когда они нужны).

Трасса на \(aabbcc\) (кратко):

Проход 1: \(a_1 \to X\), \(b_1 \to Y\), \(c_1 \to Z\), возврат.

Проход 2: \(a_2 \to X\), \(b_2 \to Y\), \(c_2 \to Z\), возврат.

Проход 3: \(q_0\) видит \(Y\) (больше нет \(a\)) → вход в \(q_4\) → только \(Y\) и \(Z\) → принять.